package gblend.exactquery;




/*
* Copyright 2009, Center for Advanced Information Systems,Nanyang Technological University
*
* File name: UllmanVerify.java
*
* Abstract: Ullman subgraph isomorphism verification
*
* Current Version:      0.1
* Auther:               Jin Changjiu
* Modified Date:        Jun.16,2009
*
*/


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */


import gblend.adjlistgraph.ALGraph;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.Collections;
import java.util.Vector;
import gblend.frequentindex.Vertex;
import gblend.infrequentindex.Nodecompare;
/**
 *
 * @author cjjin
 */
public class NewUllmanVerify {

    private  Vector<ALGraph> graphlist = new Vector<ALGraph>();
    private  ALGraph  tmpgraph = null;
    private Vector<Integer> nodeset = new Vector<Integer>();

    public static void main (String[] args) throws FileNotFoundException
    {
        NewUllmanVerify u = new NewUllmanVerify();
        u.formatDotFile("test1.txt");
    }



    public  boolean verify(ALGraph q, ALGraph g)
    {
         nodeset.clear();
        //initialize the ullman algorithm
         int a1 = g.getNnum();//node number of graph
         Vector<Integer> F = new Vector<Integer>();
         for(int i = 0; i< a1;i++)
         {
            F.addElement(0);
         }
         int b1 = q.getNnum();//node number of query
         Vector<Integer> H = new Vector<Integer>();
         for(int i = 0; i< b1;i++)
         {
            H.addElement(0);
         }
         int d = 0;//depth

         int[][]M = new int[b1][a1];
         for(int i = 0; i< b1;i++)
         {
             for(int j = 0; j< a1;j++)
             {
                if(q.getNode(i).getDegree()<=g.getNode(j).getDegree()
                        &&q.getNode(i).getLabel().equals(g.getNode(j).getLabel()))
                {
                    M[i][j]=1;
                }
                else
                {
                    M[i][j]=0;
                }
             }

         }

        return  UllmanAlgo(F,H,q,g,d,M);

    }

    //the ullmanalgorim verification
    public  boolean UllmanAlgo(Vector<Integer>F,Vector<Integer>H,ALGraph q,ALGraph g,int d,int[][]M)
    {

        int a = g.getNnum();
        int b = q.getNnum();

        if(d==b)//check all the nodes of query
        {
            return true;
        }
        else
        {
            for(int k = 0; k<a;k++)
            {
             if(F.elementAt(k)==0&&refine(q,g,d,k,M))
              {
                    H.setElementAt(k, d);
                    F.setElementAt(1, k);

                    int[][]M1 = new int[b][a];
                    for(int n = 0;n < b;n++)
                       for(int m = 0;m < a;m++)
                       {
                            M1[n][m]=M[n][m];
                       }

                    for(int m = 0;m < a;m++)
                    {
                        if(m!=k)
                        M[d][m]=0;
                    }

                    if(UllmanAlgo(F,H,q,g,d+1,M))
                    {
                        nodeset.addElement(k);
                        return true;
                    }
                    else
                    {
                        M=M1;
                        F.setElementAt(0, k);
                    }
               }

            }//end for
        }//end else
        return false;
   }


    public Vector<Vertex> getNeighbors(int nid,ALGraph q)
    {
        Vector<Vertex> neighbor = new Vector<Vertex>();
        for(int i = 0; i<q.getNnum();i++)
        {
            if(q.getEdge(i, nid)>0)
            {
                neighbor.addElement(q.getNode(i));
            }
        }

        Nodecompare nc = new Nodecompare();
        Collections.sort(neighbor,nc);

        return neighbor;
    }


   //refine process
    public  boolean refine(ALGraph q, ALGraph g,int d,int k,int[][]M)
    {
        Vector<Integer> visited = new Vector<Integer>();

        if(M[d][k]==1)
        {
             Vector<Vertex> nset=getNeighbors(d,q);
             for(int i = 0; i<nset.size();i++)
             {
                  int x = nset.elementAt(i).getId();
                  int y=0;
                  for(y = 0; y<g.getNnum();y++)
                  {
                    if(!visited.contains(y)&&g.getEdge(y,k)==1 &&M[x][y]==1)
                    {
                       visited.addElement(y);
                       break;
                     }

                   }//end y
                   if(y==g.getNnum())
                   {
                     M[d][k]=0;
                     return false;
                   }
             }
        }
        else
        {
            return false;
        }
        return true;

    }

    public Vector<Integer> getNodeset()
    {
        return nodeset;
    }


    /**********************************************************************/
    public  void formatDotFile(String filename)
    {
	String strLine = null;
	FileInputStream inStream;
	DataInputStream in;
	BufferedReader br;

	File fin=new File(filename);

	if(fin.exists())
	{
            try {
       		inStream=new FileInputStream(fin);
                in = new DataInputStream(inStream);
                br = new BufferedReader(new InputStreamReader(in));
		//Read file line by line
                try {
                      int graphnum = -1;
                      while ((strLine = br.readLine()) != null)
                      {
                       // Print the content on the console
                       if(strLine.contains("t #"))
                       {
                           String[] line = strLine.split("\\s");
                           tmpgraph = new ALGraph(Integer.parseInt(line[3]));
                           tmpgraph.setNnum(Integer.parseInt(line[3]));
                           graphnum++;
                       }
                       else if(strLine.contains("v"))
                       {
                           String[] line = strLine.split("\\s");
                           Vertex  node = new Vertex();
                           node.setId(Integer.parseInt(line[1]));
                           node.setLabel(line[2]);
                           tmpgraph.addnode(node);
                       }
                       else if(strLine.contains("e"))
                       {
                            String[] line = strLine.split("\\s");
                            int s = Integer.parseInt(line[1]);
                            int t = Integer.parseInt(line[2]);
                            tmpgraph.addEdge(s, t);
                            tmpgraph.getNode(s).setDegree();
                            tmpgraph.getNode(t).setDegree();

                       }
                        else
                       {
                          graphlist.addElement(tmpgraph);
                       }

                      }

                      if(verify(graphlist.elementAt(0),graphlist.elementAt(1)))
                      {
                         System.out.println(graphlist.elementAt(1).getNnum()+" Correct!");
                      }
                      else
                      {
                         System.out.println(graphlist.elementAt(1).getNnum()+"Fail!");
                      }
        
                      in.close();

		   }
		   catch (IOException e)
		   {
			// TODO Auto-generated catch block
			e.printStackTrace();
		   }
               } catch (FileNotFoundException e) {
		// TODO Auto-generated catch block
                    e.printStackTrace();
               }
	}

  }


}
